Jump to content

Talk:Quantifier (logic)

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Why is A "inverted" and E "rotated"?

[edit]

Both can be described as a 180 degree rotation, and both can be described as a reflection (albeit over different axes).

38.111.154.107 (talk) 15:19, 19 August 2014 (UTC)[reply]

I guess, both orignated from rotation, which is easily realized in pre-computer typesetting, while reflection is not. However, that might need a source, which I haven't. - Jochen Burghardt (talk) 18:22, 19 August 2014 (UTC)[reply]

formal semantics, and an omission?

[edit]

formal semantics seems a bit tough here. A x e S (P(x)) (all x element of set S then P(x)) means, *informally*, for a set S = {wilma, harry, bob,...}, that P(wilma) /\ P(harry) /\ P(bob) /\ ... Also I can't see a def of All and Exists for the empty set. 78.149.128.58 (talk) 10:52, 14 May 2016 (UTC)[reply]

Yes, the section Quantifier (logic)#Formal semantics uses somewhat pompous language. However, it needs to explain also more general cases like
  • "∀x Q(x,x)" - when e.g. Q(wilma,wilma) is part of the conjunction, but Q(wilma,harry) is not, assuming {wilma, harry, bob,...} to be the given domain of individuals, and like
  • "P(x) → (∀x Q(x,x))" - where x occurs free and bound in P and Q, respectively.
The section does not define a semantics of formulas like "∀xS φ", so the question "what if S is empty" doesn't immediately apply there. However, "∀xS φ" and "∃xS φ" is usually defined as "∀x (xS → φ)" and "∃x (xS ∧ φ)", repectively, where "φ" denotes an arbitrary formula (that may contain "x"). From these definitions, "∀xS φ" and "∃xS φ" evaluates to true and false, respectively, when S is empty. - Jochen Burghardt (talk) 16:38, 14 May 2016 (UTC)[reply]
In classical first order logic, the domain of quantification is never empty. For logic which allows empty domains, see free logic. 31.52.253.142 (talk) 22:09, 5 July 2017 (UTC)[reply]

negation of quantifiers in intuitionistic logic

[edit]

In the section 'Equivalent expressions', it is stated that 'not(for all(...)) = there exists(not(...))' and 'not(there exists(...)) = for all(not(...))'. Does this hold also in intuitionistic logic? In the wikipedia article for Intuitionistic Logic it says "In intuitionistic first-order logic both quantifiers ∃, ∀ are needed", and this leads me to believe that it is not true. Could somebody in the know please inform us and add to the article? (or just let us know and I'll add it to the article) Even if this negation is valid in intutionistic logic, it should still be added to the article.

Relations of quantifiers to logical conjunction and disjunction (for an infinite domain of discourse)

[edit]

A section in the article says something re the connection of quantifiers to logical conjunction and disjunction, especially when the domain of discourse is infinite, claiming that an infinite sequence of logical conjunctions or disjunctions is problematic from some rather unspecified/undetalied point of view.--109.166.134.237 (talk) 14:41, 31 August 2019 (UTC)[reply]

The problematic aspect refers to "syntax rules expected to generate finite objects". Is this opposed to allowing an infinite set of finite objects?--109.166.134.237 (talk) 12:41, 1 September 2019 (UTC)[reply]

This aspect is also discussed at Talk:Formal language#Infinite words.--109.166.134.237 (talk) 12:58, 1 September 2019 (UTC)[reply]

Quantifiers per se do not create “infinite sequences”. An expansion of an order-1 formula to a propositional formula would do it, indeed. One should carefully distinguish form and interpretations when speaking about logic. Incnis Mrsi (talk) 14:08, 1 September 2019 (UTC)[reply]
So how could we adequately phrase these aspects in article section?--109.166.134.237 (talk) 14:16, 1 September 2019 (UTC)[reply]
In this context, is it about the infinity of alphabet or the infinity of the set of words in a formal language translated into a infinity of (singular) propositions joined by conjunctions or disjunctions?--109.166.134.237 (talk) 14:28, 1 September 2019 (UTC)[reply]
I'm not happy with the section Quantifier (logic)#Relations to logical conjunction and disjunction, but I still don't have a finished suggestion what to do with it.
As I understand it, the set of syntactically valid predicate logic formulas is a formal language, which is usually defined by a context-free grammar (the latter is currently given informally at First-order logic#Formation rules, a table of e.g. BNF-rules should be added there I meanwhile added a table of BNF-rules there). A formal language is a (usually infinite) set of finite-length strings (each one called a formula in our case). So a formula always has finite length, hence the infinite conjunction from the 1st example cannot be a formula. This far, I agree. (With two side remarks: 1. Infinite conjunctions of finite-length formulas are considered in model theory; this way, the first example could be handled without quantification, but the second, disjunctive, could not. - 2. In the subfield of automata theory, also sets of infinite-length strings are considered, see e.g. ω-automaton, but I never saw them in use to allow infinite-length formulas.) My personal naive opinion is that a formula is something a mathematician writes on paper; it therefore has to be of finite length.
With the paragraph speaking about "procedure" and "irrational numbers", I have problems. It seems to suggest that a formula could be some countably-infinite-length string generated by an algorithm ("procedure"). I wouldn't agree to that, and I suspect it to be WP:OR.
To comment on the above questions: Imo, an infinite alphabet is not an issue here (each natural number can be denoted by sufficiently many "s" applied to "0", requiring only a finite alphabet). Moreover, the infiniteness of the set of all syntactically valid formulas is not an issue here.
Maybe, the whole "infiniteness" stuff should be deleted in this section. We could just say, that, when talking about a finite domain of discourse (e.g. the set of 10-digit-ISBNs), a conjunction over all its elements can be abbreviated by a universal quantification (e.g. ∀n chk(n)=0, where "chk" denotes the checksum mod 11). This would explain the meaning of quantifiers. We could the just say e.g. "For an infinite domain, the meaning is similar, but quantification can no longer be expanded into conjunction/disjunction." (This phrasing needs improvement). - Jochen Burghardt (talk) 13:31, 2 September 2019 (UTC)[reply]

Comment re a formula involving an infinite number of terms or operands: A comparison can be made between series where addition involves an infinite number of addends

and a conjunctional/disjunctional formula or (Boolean formula (set operations formula with union/intersection)) with infinite number of terms.

The place of the operation of addition is taken by logical conjunction/disjunction of atomic propositions. As in the case of series where partial sums are considered, in conjunctional/disjunctional formulae partial results of the logical operations with the first n conjuncts/disjuncts can be viewed similarly to the case of series.--109.166.130.34 (talk) 12:04, 5 September 2019 (UTC)[reply]

I guess I never saw that notation. In order to assign a Tarski semantics to it, one would need to establish a metric on the set of truth values, and then define the limit of a sequence of truth values, etc. This approach would definitely need a reliable source. However, I doubt it would have any advantage over using . - Jochen Burghardt (talk) 16:09, 8 September 2019 (UTC)[reply]
The last formula is interesting and indeed equivalent to the previous one, due to the fact that the truth of a logical conjunctions of propositions is given by the truth of each proposition in the conjunction.--109.166.129.57 (talk) 22:49, 8 September 2019 (UTC)[reply]
The previous formula has an explicit presence of the conjunction operator.--109.166.129.57 (talk) 22:52, 8 September 2019 (UTC)[reply]

Cartesian products of domains of discourse in quantifier equivalences for diadic, triadic... predicates

[edit]

The equivalences of quantifier to logical conjunction and disjunction should also be presented for non-monadic predicates, namely diadic, triadic... predicates (relation predicates). In these cases each variable x, y, or x1, x2 ..has its domain of discourse Di. It seems that cartesian products of domains of discourse Di x Dj are involved.--109.166.129.57 (talk) 18:30, 9 September 2019 (UTC)[reply]

I have just noticed on Wikipedia in German de:Prädikat (Logik) the aspect presented above briefly re cartesian products of universes of discourse (Diskursuniversums). The info the German article can be also inserted here.--109.166.129.57 (talk) 01:05, 10 September 2019 (UTC)[reply]

Sequence variables xi,n and infinite set of sequences

[edit]

For a numerical sequence (Proth number, Cullen number, etc) where all term share a common property (like being prime or composite, divisible with an individual number, etc) also an infinite set of sentences re the individual elements of the universe of discourse appears, as mentioned at talk:open formula.--109.166.129.57 (talk) 03:02, 10 September 2019 (UTC)[reply]

Existential quantifier attached to predicate scheme re the result of an operation with an infinite number of terms/operands

[edit]

I have encountered on some talk page a statement about a predicate scheme involving the result of an operation with an infinite number of operands stated like the following:

There are infinite sums of rational numbers which are irrational numbers.--109.166.129.57 (talk) 15:46, 10 September 2019 (UTC)[reply]

I'd formalize this in 2nd-order logic as "(∃F:ℕ→ℚ) (∑
i=0
F(i)) ∈ ℝ\ℚ". No infinite con- or disjunction is involved, so what is your point here? - Jochen Burghardt (talk) 19:37, 10 September 2019 (UTC)[reply]
Of course there is no involvement of infinite con- or disjunction in this example, just that I was very intrigued by the possibility of such case when encountering it and I wondered how can this be represented with predicate schemes in this case where the result of an operation with infinite number of operands is ascribed a predicate (is an irrational number). It is also very intriguiging your proposal of representation/formalization, especially the aspects about 2nd order logic. I also want to search for a specific example of such a procedure to generate irrational numbers.--109.166.129.57 (talk) 19:59, 10 September 2019 (UTC)[reply]
The procedure is quite simple: Starting from e.g. sqrt(2) which is known to be irrational, compute its decimal expansion 1.4142..., then split it digit by digit, expressing the latter as rational numbers: sqrt(2) = 1/1+4/10+1/100+4/1000+2/10000+... - I still doubt that anyone has investigated infinite predicate schemes; did you find a source for that meanwhile? - Jochen Burghardt (talk) 20:21, 10 September 2019 (UTC)[reply]
[edit]

@Jochen Burghardt: Hi, no target page is Operator (mathematics) and the content is about operator in general sense. Here

an operator is generally a mapping or function

explicitly says "generally". And here:

The most basic operators (in some sense) are linear maps, which act on vector spaces. However, when using "linear operator" instead of "linear map", mathematicians often mean actions on vector spaces of functions, which also preserve other properties, such as continuity.

i.e., explicitly says that the article is speaking about more general term than linear operator. I really think that the hyperlink is correct and should be placed there. Thanks, Hooman Mallahzadeh (talk) 15:38, 24 April 2021 (UTC)[reply]

A quantifier is neither a mapping nor a function (what would be its domain and range?), so this article is about a different meaning of "operator" than used in Quantifier (logic). Operator (mathematics) doesn't contain any explanation that is useful to people reading Quantifier (logic). - Jochen Burghardt (talk) 16:13, 24 April 2021 (UTC)[reply]
@Jochen Burghardt: You are right, but is quantifier a "symbol" or an "operator"? I have an idea, first line that now is:

In logic, a quantifier is an operator that specifies how many individuals in the domain of discourse satisfy an open formula.

becomes
In logic, a quantifier is a logical concept that specifies how many individuals in the domain of discourse satisfy an open formula.
Is that change correct? Hooman Mallahzadeh (talk) 16:42, 24 April 2021 (UTC)[reply]
"Symbol" would be ok, except that a quantifier comes with a variable, so they are 2 symbols. "Logical concept" avoids this problem, but is *very* general. Moreover, "quantification is a logical concept" would be more appropriate, I guess. The article modal operator uses "operator or (logical) connective", and logical connective uses "operator or (logical) constant". Logical constant uses "symbol"; in the table of examples, it lists (among others) quantifiers and modal operators. All these articles apparently use "operator" in a rather colloquial sense. "Connective" has the problem that it refers to something that connects two formulas, while a quantifier work on one. "Constant" has the same problem as "symbol". To summarize, I still think using the common-sense-language meaning of "operator" is the best. - Jochen Burghardt (talk) 17:59, 24 April 2021 (UTC)[reply]

Sharpen distinction w.r.t. bounded quantifier

[edit]

There's a question on the talk page of bounded quantifier that asks: "Isn't every quantifier bounded?" which is actually a reasonable question. If one is breezy and casual, the distinction between the two is "obvious", but if you think more deeply, there's a "hey wait a minute" moment. Part of the problem is that this article is shot full of discussion about the "domain of discourse", which makes it sound like every quantifier is a bounded quantifier. Yet the distinction is important: the bounded quantifiers sit at the bottom of the Lévy hierarchy, which is used to talk about ZF. For arithmetic, they sit at the bottom of the arithmetical hierarchy. Likewise, the axiom schema of predicative separation also asks for bounded quantifiers only.

The fix, I think, is to have this article have a subsection that says something like "a quantifier is called unbounded when the domain of discourse is the entire universe" and then explain what universe is. And then explain that bounded quantifiers are for sub-sets (sub-classes?) of the universe. I don't know enough set theory to say the above formally correctly, but you catch my drift, right? 67.198.37.16 (talk) 20:35, 28 November 2023 (UTC)[reply]

Paucal and multal quantifier source?

[edit]

I looked up paucal and multal quantifiers, and I could find almost no sources. A few broken or highly modified forums and an article on the Polish language were all I could find. If anyone could specify where among the sources this topic is described, I would appreciate that. IsaacPhilo (talk) 20:34, 6 December 2023 (UTC)[reply]

These terms seem to originate from linguistics. The section Grammatical_number#Paucal has some references (about particular natural languages). Maybe there are linguistics textbooks or journal articles on the subject? - Jochen Burghardt (talk) 07:47, 7 December 2023 (UTC)[reply]